package 二叉树;

import 链表.ListNode;

public class JZ26树的子结构 {

    /**
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
     * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     *
     * 例如:
     * 给定的树 A:
     *
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     * 给定的树 B：
     *
     *    4 
     *   /
     *  1
     * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
     *
     * 示例 1：
     * 输入：A = [1,2,3], B = [3,1]
     * 输出：false
     * 示例 2：
     * 输入：A = [3,4,5,1,2], B = [4,1]
     * 输出：true
     * 限制：
     * 0 <= 节点个数 <= 10000
     */

    private TreeNode B;

    public boolean isSubStructure(TreeNode A, TreeNode B) {

        if(A==null||B==null){
            return false;
        }
        this.B=B;
        return this.dfs(A);
    }

    private boolean dfs(TreeNode A) {

        if(A==null){
            return false;
        }

        if(A.val==this.B.val){
            if(isChildrenTree(A,B)){
                return true;
            }
        }

        return dfs(A.left)||dfs(A.right);
    }

    private boolean isChildrenTree(TreeNode A, TreeNode B) {

        if(B==null){
            return true;
        }

        if(A == null){
            return false;
        }

        if(A.val!=B.val){
            return false;
        }

        return isChildrenTree(A.right,B.right)&&isChildrenTree(A.left,B.left);
    }

    public static void main(String[] args) {
        JZ26树的子结构 jz=new JZ26树的子结构();
        TreeNode treeNode1 = TreeNode.getNodeByArr(new Integer[]{10, 12, 6, 8, 3, 11});
        treeNode1.printNode();
        TreeNode treeNode2 = TreeNode.getNodeByArr(new Integer[]{10,12,6,8});
        treeNode2.printNode();
        boolean result = jz.isSubStructure(treeNode1, treeNode2);
        System.out.println(result);
    }

}
